#include <iostream>
#include "BinaryTree.h"
using namespace std;

// 99.30 %
class Solution1
{
  public:
	int sumOfLeftLeaves(TreeNode *root)
	{
		if (!root || !root->left && !root->right)
			return 0;
		if (!root->left)
			return sumOfLeftLeaves(root->right);
		if (!root->left->left && !root->left->right)
			return root->left->val + sumOfLeftLeaves(root->right);
		if (root->left && root->right)
			return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
		if (root->left && !root->right)
			return sumOfLeftLeaves(root->left);
		if (!root->left && root->right)
			return sumOfLeftLeaves(root->right);
	}
};
// 99.30 %
class Solution
{
  public:
	int sumOfLeftLeaves(TreeNode *root)
	{
		if (!root || !root->left && !root->right)
			return 0;
		if (!root->left)
			return sumOfLeftLeaves(root->right);
		if (!root->left->left && !root->left->right)
			return root->left->val + sumOfLeftLeaves(root->right);
		return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
	}
};

int main()
{
	int arr[] = {3, 9, 0, 0, 20, 15, 0, 0, 7, 0, 0};
	int n = sizeof(arr) / sizeof(arr[0]);
	TreeNode *tree = createBinaryTree(arr, n);
	preorderPrint(tree);
	cout << endl;
	cout << Solution().sumOfLeftLeaves(tree) << endl;
	return 0;
}
